#include "binarySearchTree.h"
#include <stdlib.h>
#include "../logger/logger.h"
SearchTree MakeEmpty(SearchTree T)
{
    if (T != NULL)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

//return position of x in T, the left store smaller number
Position Find(ElementType x, SearchTree T)
{
    if (!T)
        return NULL;
    if (x < T->Element)
        return Find(x, T->Left);
    else if (x > T->Element)
        return Find(x, T->Right);
    else
        return T;
}

//find min ele's position
Position FindMin(SearchTree T)
{
    if (!T)
        return NULL;
    if (T->Left == NULL)
        return T;
    else
        return FindMin(T->Left);
}

//find max ele's position
Position FindMax(SearchTree T)
{
    if (!T)
        return NULL;
    if (T->Right == NULL)
        return T;
    else
        return FindMax(T->Right);
}

//insert x into T
SearchTree Insert(ElementType x, SearchTree T)
{
    if (!T)
    {
        T = malloc(sizeof(*T));
        if (!T)
            FatalError("out of space!");
        else
        {
            T->Element = x;
            T->Left = NULL;
            T->Right = NULL;
        }
    }
    else
    {
        if (x < T->Element)
            T->Left = Insert(x, T->Left);
        else if (x > T->Element)
            T->Right = Insert(x, T->Right);
    }
    return T;
}

//delete x from T
//if x is leaf, delete it at once
//if x has one son, let it's parent take control it's son
//if x has two sons, use it's left son's smallest node to replace it
SearchTree Delete(ElementType x, SearchTree T)
{
    Position TmpCell = T;
    if (!T)
        return T;
    if (x < T->Element)
        T->Left = Delete(x, T->Left);
    else if (x > T->Element)
        T->Right = Delete(x, T->Right);
    //have two sons
    else if (T->Right && T->Left)
    {
        //找到右子树中最小的节点替代本节点，然后将那个节点递归的从右子树中删除
        //最小的节点必定是叶子节点
        TmpCell = FindMin(T->Right);
        T->Element = TmpCell->Element;
        T->Right = Delete(T->Element, T->Right);
    }
    else if (T->Right || T->Left)
    {
        if (T->Left == NULL)
            T = T->Right;
        else
            T = T->Left;
        free(TmpCell);
    }
    //have no sons
    else
    {
        free(T);
        T = NULL;
    }
    return T;
}

static void Print(SearchTree T, int Depth, int Right)
{
    if (!T)
        return;
    for (int i = 0; i < Depth; i++)
        printf(" ");
    printf("%d:%s\n", T->Element, Right ? "右" : "左");
    Print(T->Left, Depth + 1, 0);
    Print(T->Right, Depth + 1, 1);
}

void PrintTree(SearchTree T)
{
    Print(T, 0, 0);
}
